package arithmetic.leetCode;

/**
 * @author dycong
 * @date 2019/9/14 13:53
 */
public class OfLongestSubstring_3 {

    public static void main(String[] args) {
        String str = "abcbacd";
        System.out.println(lengthOfLongestSubstring(str));
        System.out.println(lengthOfLongestSubstring_(str));
    }

    /**
     * 滑动窗口 非初始化 -1 版
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring_(String s) {
        int max = 0, left = 1, right = 1;
        int[] allChar = new int[256];
        for (int i = 1; i <= s.length(); i++) {
            char c = s.charAt(i-1);
            right = i;
            int lastIndex = allChar[c];
            //滑动窗口
            if (lastIndex != 0) {
                left = Math.max(left, lastIndex + 1);
            }

            allChar[c] = i;
            max = Math.max(max, right - left + 1);
        }
        return max;
    }

    /**
     * 滑动窗口
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        int max = 0, left = 0, right = 0;
        int[] allChar = new int[256];
        for (int i = 0; i < allChar.length; i++) {
            allChar[i] = -1;
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            right = i;
            int lastIndex = allChar[c];
            //滑动窗口
            if (lastIndex != -1) {
                left = Math.max(left, lastIndex + 1);
            }

            allChar[c] = i;
            max = Math.max(max, right - left + 1);
        }
        return max;
    }

    public static int lengthOfLongestSubstring_2(String s) {
        //对应 char ascii 码值下标存储了该char 最新出现过的位置
        int[] allChar = new int[256];
        for (int i = 0; i < allChar.length; i++) {
            allChar[i] = -1;
        }
        int res = 0;
        //子串的起点下标记.
        int left = -1;
        for (int i = 0; i < s.length(); i++) {
            //left 就是遍历之前的没有出现过的字符,定义本串起点
            left = Math.max(left, allChar[s.charAt(i)]);
            //更新出现过的字符位置.
            allChar[s.charAt(i)] = i;
            //遍历到当前字符串,最大的要么之前的最大的长,
            // 要么就是 left到当前字符的步长.
            res = Math.max(res, i - left);
        }
        return res;
    }

}
